import Model from '../ModelAlgorithm'

// 从网上抄来的算法
function algorithm(arr) {
  console.log('当前调用希尔排序：')

  const len = arr.length

  // 开展缩小增量计算，在gap = 0 之前，不断对增量进行缩小计算
  // 这里采取右移一位的向下取整方案
  for (var gap = len >> 1; gap > 0; gap = gap >> 1) {
    // 首先这里看起来是分成了两个大组，事实上它意味着是每两个元素分成一组
    // 目前看来，这个gap的选择，最好能被排序数组长度整除
    // j-gap 是算出对应分组元素
    for (var i = gap; i < len; i++) {
      var j = i
      var current = arr[i]
      while (j - gap >= 0 && current < arr[j - gap]) {
        arr[j] = arr[j - gap]
        j = j - gap
      }
      arr[j] = current
    }
    console.log(arr)
  }

  return arr
}

function description() {
  return {
    title: '希尔排序(缩小增量排序)-Shell',
    desc: [
      '它是插入排序的改进',
      '关键是算法增量gap的计算方式，初始增量、缩小增量的计算公式对排序效率有关键影响',
      '希尔所推荐的<b>增量序列</b>为：[n/2, (n/2)/2, ...., 1]',
      '这是一个时间复杂度突破了O(n<sup>2</sup>)的算法'
    ],
  }
}

export default (runner) => {
  const entity = new Model(algorithm, description())
  runner.injectAlgorithm('shell', entity)
}
